#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <sstream>
#include <list>
#include <stack>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
    bool isValid(string s) {
        stack<char> mst ;
        int len = s.length();
        if(len %2 == 1) return false;
        for(int i=0 ;i< len ;i++ ){
            char c = s.at(i);
            if( c == '{' || c == '[' || c == '(' ) mst.push(c) ;
            else if ( !mst.empty() && ( (c == ')' && mst.top() == '(') || (c == ']' && mst.top() == '[') || (c == '}' && mst.top() == '{')) ) mst.pop();
            else return false;
        }
        return mst.empty();
    }
};


int main(){

    vector < vector<int> > ans;
    Solution sp;
    vector<int> nums = {1,0,-1,0,-2,2};
    string s = "){";
    cout<< (bool)sp.isValid(s) <<endl;
    return 0;
}